#include <bits/stdc++.h>

using namespace std;

// 按公因数计算最大组件大小
// 给定一个由不同正整数的组成的非空数组 nums
// 如果 nums[i] 和 nums[j] 有一个大于1的公因子，那么这两个数之间有一条无向边
// 返回 nums中最大连通组件的大小。
// 测试链接 : https://leetcode.cn/problems/largest-component-size-by-common-factor/
// 提交以下 Solution 类，可以通过所有测试用例

class Solution 
{
public:
    static const int MAXV = 100001;
	// factors[a] = b
	// a这个质数因子，最早被下标b的数字拥有
    int factors[MAXV];
    // 讲解056、讲解057 - 并查集模版
    static const int MAXN = 20001;
    int father[MAXN];
    int size[MAXN];
    int n;

    // 对并查集进行初始化
    void build()
    {
        for(int i = 0; i < n; ++i)
        {
            father[i] = i;
            size[i] = 1;
        }
        memset(factors, -1, sizeof factors);
    }

    // 找 i 的父节点并进行路径压缩
    int find(int i)
    {
        return i == father[i] ? i : father[i] = find(father[i]);
    }

    // 将 x 和 y 所在的集合进行合并
    void unionSet(int x, int y)
    {
        int fx = find(x);
        int fy = find(y);
        if(fx != fy)
        {
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }

    // 返回最大的集合
    int maxSize()
    {
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            ans = max(ans, size[i]);
        }
        return ans;
    }

	// 正式方法
	// 时间复杂度O(n * 根号v)
    int largestComponentSize(vector<int>& nums) 
    {
        n = nums.size();
        build();
        for(int i = 0, x; i < n; ++i)
        {
            // 质因数分解
            x = nums[i];
            for(int j = 2; j * j <= x; ++j)
            {
                if(x % j == 0)
                {
                    if(factors[j] == -1) factors[j] = i;
                    else unionSet(factors[j], i);
                    // 将 j 质因子除尽
                    while(x % j == 0) x /= j;
                }
            }
            // 还有一个质因子
            if(x > 1)
            {
                if(factors[x] == -1) factors[x] = i;
                else unionSet(factors[x], i);
            }
        }
        return maxSize();
    }
};

// 打印所有n的质因子，时间复杂度O(根号n)
void f(int n)
{
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            cout << i << endl;
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1) cout << n << endl;
}

int main()
{
    // 数字n拆分质数因子
    int n = 4012100;
    f(n);

    return 0;
}